class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_max(n, nums[0]);
        vector<int> dp_min(n, nums[0]);
        int ret = nums[0];

        for (int i = 1; i < n; i++)
        {
            dp_max[i] = max(nums[i], max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]));
            dp_min[i] = min(nums[i], min(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]));
            ret = max(ret, dp_max[i]);
        }

        return ret;
    }
};